#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define Maxsize 100
typedef char ElemType;

typedef struct node
{
    ElemType value;
    struct node *lchild;
    struct node *rchild;
} BTNode;

void CreateBTree(BTNode *&b, char *str)
{
    BTNode *St[Maxsize], *p;    //数组模拟栈，用于存储双亲节点
    int top = -1, k = 0, i = 0; // k是标志位，1代表左子树，2代表右子树
    char ch;                    //用于遍历字符串
    b = NULL;                   //初始化根节点
    ch = str[i];
    while (ch != '\0')
    {
        switch (ch)
        {
        case '(':
            top++;
            St[top] = p;
            k = 1;
            break;
        case ',':
            k = 2;
            break;
        case ')':
            St[top--];
            break;
        default:
            p = (BTNode *)malloc(sizeof(BTNode));
            p->lchild = NULL;
            p->rchild = NULL;
            p->value = ch;
            if (b == NULL)
            {
                b = p;
            }
            else
            {
                switch (k)
                {
                case 1:
                    St[top]->lchild = p;
                    break;
                case 2:
                    St[top]->rchild = p;
                    break;
                }
            }
            break;
        }
        ch = str[++i];
    }
}

void DestoryBTree(BTNode *&b)
{
    if (b != NULL)
    {
        DestoryBTree(b->lchild);
        DestoryBTree(b->rchild);
        free(b);
    }
}

BTNode *FindNode(BTNode *b, ElemType x)
{
    BTNode *p;
    if (b == NULL)
    {
        return NULL;
    }
    else if (b->value == x)
    {
        return b;
    }
    else
    {
        p = FindNode(b->lchild, x);
        if (p != NULL)
        {
            return p;
        }
        else
        {
            return FindNode(b->rchild, x);
        }
    }
}

BTNode *LchildNode(BTNode *p)
{
    return p->lchild;
}

BTNode *RchildNode(BTNode *p)
{
    return p->rchild;
}

int BTHeight(BTNode *b)
{
    int lchildh, rchildh;
    if (b == NULL)
    {
        return 0;
    }
    else
    {
        lchildh = BTHeight(b->lchild);
        rchildh = BTHeight(b->rchild);
        return lchildh > rchildh ? (lchildh + 1) : (rchildh + 1);
    }
}

void DispBTree(BTNode *b)
{
    if (b != NULL)
    {
        printf("%c", b->value);
        if (b->lchild != NULL || b->rchild != NULL)
        {
            printf("(");
            DispBTree(b->lchild);
            printf(",");
            DispBTree(b->rchild);
            printf(")");
        }
    }
}
